package violencerecursion;

/**
 * @author tongchen
 * @create 2023-03-27 9:30
 */
public class DpBag {
    public static void main(String[] args) {

    }

    //实现动态规划的方法

    /**
     *
     * @param v 每个元素的价值
     * @param w 每个元素的重量
     * @param bag 背包剩余容量
     *  思路：创建动态规划数组，int[N+1][REST],rest是剩余容量，N代表具体的每个元素
     * @return
     */
    public int dpWay(int[]v,int[]w,int bag){
        int N=v.length;
        //创建动态规划数组
        int[][]dp=new int[N+1][bag+1];
        for(int index=N-1;index>=0;--index){
            for(int rest=0;rest<=bag;++rest){
                //当前位置不放置元素
                int p1=dp[index+1][rest];
                //放置元素
                int p2=-1;
                if(rest-w[index]>=0){
                    p2=v[index]+dp[index+1][rest-w[index]];
                }
                dp[index][rest]=Math.max(p1, p2);
            }

        }
        return dp[0][bag];
    }
}
